Write Python program to sort n numbers using Merge sort algorithm. Discuss the complexity of algorithm used.

Code:

def mergesort(nlist):

    print("Splitting",nlist)

    if len(nlist)>1:

        mid=len(nlist)//2

        lefthalf=nlist[:mid]

        righthalf=nlist[mid:]

 

        mergesort(lefthalf)

        mergesort(righthalf)

        i=j=k=0

        while i<len(lefthalf)and j<len(righthalf):

            if lefthalf[i]<righthalf[j]:

                nlist[k]=lefthalf[i]

                i=i+1

            else:

                nlist[k]=righthalf[j]

                j=j+1

            k=k+1

        while i<len(lefthalf):

            nlist[k]=lefthalf[i]

            i=i+1

            k=k+1

        while j<len(righthalf):

            nlist[k]=righthalf[j]

            j=j+1

            k=k+1

    print("Merging",nlist)

nlist=[14,46,43,27,57,41,45,21,70]

mergesort(nlist)

print(nlist)

Fundamental of algorithm

Fundamental of algorithm